Segment Tree
Operations
モノイド$ Mの列$ (a_1, a_2, \dots, a_n)を扱う.
空間計算量$ \Theta(n)
$ \mathtt{new}()
列の項がすべて$ Mの単位元であるSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{build}(a_1, a_2, \dots, a_n)
与えられた列を表現するSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{set}(i, x)
$ a_iに$ xを代入する.
時間計算量$ \Omicron(\log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l+1} \cdot \dots \cdot a_rを計算する.
時間計算量$ \Omicron(\log n)
Summary
https://gyazo.com/928b1fdc99b7000a0946c92fc33878bc
列のすべての区間をたかだか$ \log n個の重ならない区間に分割する
$ \mathtt{set}
https://gyazo.com/8699ae544f20c9552678904629a7c6db
$ \mathtt{fold}
https://gyazo.com/d4d963706b405f0dc456df884b638099
References
Notes
添字は0-based, 1-basedの2通り
考えているノード番号を$ iとする
0-based
配列の長さ: $ 2N - 1 ($ Nは$ n < Nとなる2冪の数)
親: $ (i - 1) / 2
右の子: $ 2i + 1
左の子: $ 2i + 2
$ k番目の葉: $ k + N - 1
1-based
配列の長さ: $ 2N ($ Nは$ n < Nとなる2冪の数)
親: $ i / 2
右の子: $ 2i
左の子: $ 2i + 1
$ k番目の葉: $ k + N
$ \mathtt{fold}を非再帰で書く方法がある.
定数倍が軽い
1-basedがおすすめ
$ \Omicron(\log n)で列を二分探索できる.
配列の長さを$ 2nにする実装が存在する (非再帰, 1-based)
Implementations
再帰
非再帰
Problems
imos法